'''
https://leetcode.cn/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/description/?envType=study-plan-v2&envId=graph-theory
'''
from typing import List


class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        for u, v in connections:
            graph[u].append((v, 1))
            graph[v].append((u, 0))

        res = 0
        q = [0]
        visited = [False] * n
        while q:
            u = q.pop()
            visited[u] = True
            for v, w in graph[u]:
                if visited[v]: continue
                res += w
                q.append(v)
        return res
n = 3
connections = [[1,0],[2,0]]
print(Solution().minReorder(n, connections))
